#include "./sortdatatype.h"

// 直接选择排序
/**
 * 思想:
 *
 * 时间复杂度为 O(N^2)
 * 空间复杂度为 O(1)
 *
 * 最坏情况时间复杂度为 O(N^2)
 * 最佳情况的时间复杂度为 O(N)
 */
void directSelectSort(SeqList R, int len)
{
    RecType temp;
    // 从未排序部分逐步选择最小的元素并放到已排序部分末尾
    for (int i = 0; i < len - 1; i++)
    {
        printf("NO.%d--------------------------------\n", i);
        // 在末排序部分中找到最小的元素索引
        int mindex = i;
        printf(">>defalut min: index=%d, value=%d\n", mindex, R[mindex].key);
        for (int j = i + 1; j < len; j++)
        {
            if (R[j].key < R[mindex].key)
            {
                mindex = j;
                printf(">>min: index=%d, value=%d\n", mindex, R[mindex].key);
            }
        }

        if (mindex == i)
        {
            printf("It's already sorted out\n\n");
            continue;
        }

        // 可优化, 如果找到的最小值和默认最小值下标相等, 则不需要交换位置
        printf("+++find min: index=%d, value=%d\n", mindex, R[mindex].key);
        temp = R[i];
        R[i] = R[mindex];
        R[mindex] = temp;
        printf("--exchange with defalut min: ");
        printSeqList(R, len);
        printf("\n");
    }
}

// 堆排序
/**
 * 思想:  基于二叉堆数据结构的排序算法
 *
 * 时间复杂度为 O(N*log2N)
 * 空间复杂度为 O(1)
 *
 * 最坏情况时间复杂度为 O(N*log2N)
 * 最佳情况的时间复杂度为 O(N)
 */
void heapify(SeqList R, int n, int i);
void heapSort(SeqList R, int len)
{
    // 构建大顶堆
    for (int i = len / 2 - 1; i >= 0; i--)
    {
        heapify(R, len, i);
    }

    // 逐个将堆顶元素与末尾元素交换，并重新构建堆
    for (int i = len - 1; i > 0; i--)
    {
        // 将当前最大值（堆顶元素）放到数组末尾
        RecType temp = R[0];
        R[0] = R[i];
        R[i] = temp;

        // 重新构建堆
        heapify(R, i, 0);
    }
}

// 重新构建堆
void heapify(SeqList R, int n, int i)
{
    int largest = i;       // 初始化最大值为根节点
    int left = 2 * i + 1;  // 左子节点索引
    int right = 2 * i + 2; // 右子节点索引

    // 如果左子节点大于根节点，则更新最大值
    if (left < n && R[left].key > R[largest].key)
        largest = left;

    // 如果右子节点大于最大值，则更新最大值
    if (right < n && R[right].key > R[largest].key)
        largest = right;

    // 如果最大值不是根节点，则交换根节点和最大值，并重新构建堆
    if (largest != i)
    {
        RecType temp = R[i];
        R[i] = R[largest];
        R[largest] = temp;

        // 递归地进行堆化操作
        heapify(R, n, largest);
    }
}

int main()
{

    int arr[] = {67, 56, 45, 36, 35, 28, 18, 13};
    int len = sizeof(arr) / sizeof(arr[0]);
    SeqList R;
    init(R, arr, len);
    printf("-------------directSelectSort---------------\n");
    directSelectSort(R, len);
    printSeqList(R, len);

    init(R, arr, len);
    printf("-------------headSort---------------\n");
    heapSort(R, len);
    printSeqList(R, len);

    return 0;
}